//
// Created by Administrator on 2021/12/27.
//

#ifndef CPP_LEARNING_VECTOR_HPP
#define CPP_LEARNING_VECTOR_HPP
typedef int Rank;
#define DEFAULT_CAPACITY 2
#include <iostream>
#include "utils.h"
template <typename T>
class Vector{
protected:
    Rank _size; int _capacity; T* _elem;

    void copyFrom( T const*A, Rank lo, Rank hi);
    void expand();
    void shrink();
    void bubble(Rank lo, Rank hi);
    void bubbleSort(Rank lo, Rank hi);

    void selectionSort(Rank lo, Rank hi);
    void merge(Rank lo, Rank mi, Rank hi);

    Rank partition(Rank lo, Rank hi);
    void quickSort(Rank lo, Rank hi);
    void heapSort(Rank lo, Rank hi);

    // 构造函数
    Vector(int c = DEFAULT_CAPACITY, int s = 0, T v = 0){// 容量为C 规模为s
        _capacity = c;
        _elem = new T[_capacity];
        for(_size=0;_size < s;_size++){
            _elem[_size] = v;
        }
    }

    Vector(T const *A, Rank n){copyFrom(A,0,n);}
    Vector(T const *A, Rank lo, Rank hi) {copyFrom(A, lo ,hi);}
    Vector(Vector<T>const & V) { copyFrom(V._elem, 0, V._size);}
    Vector(Vector<T>const & V, Rank lo , Rank hi){copyFrom(V._elem, lo, hi);}

    // 析构函数
    ~Vector(){delete [] _elem;}

    // 只读访问接口
    Rank size() const{return _size;} //
    bool empty() const {return !_size;}
    int disordered() const;  // 判断向量是否已经排序

    Rank find(T const& e)const{}                    // 无序向量的整体查找
    Rank find(T const& e, Rank lo, Rank hi)const;   // 无序向量的区间查找

    Rank search(T const& e) const;
    Rank search(T const& e, Rank lo, Rank hi) const;

    // 可写
    T& operator[](Rank r) const;

    Vector<T>& operator=(Vector<T>const&);
    T remove(Rank r);
    int remove(Rank lo, Rank hi);
    Rank insert(Rank r, T const& e);
    Rank insert(T const& e){return insert(_size, e);}



    void sort(Rank lo, Rank hi);
    void sort(){
        sort(0,_size);
    }
    void unsort(Rank lo, Rank hi);
    void unsort(){
        unsort(0,_size);
    }

    int deduplicate(); // 无序去重
    int uniquify();    // 有序去重

    // 遍历
    void traverse(void(*pFunction)(T&));   // 使用函数指针遍历, 只读或局部修改
    template<typename VST>
    void traverse(VST &);


};

template <typename T>
void Vector<T>::copyFrom( T const *A, Rank lo, Rank hi) {
    _capacity = 2*(hi - lo);
    _elem = new T[_capacity];
    _size = 0;
    for (int i=lo;i<hi;i++){
        _elem[i] = A[lo + i];
        _size ++;
    }
}

// 拷贝复制函数
template <typename T>
Vector<T> & Vector<T>::operator=(const Vector<T> & V) {
    if( this == &V){
        return *this;
    }

    // 删除原先的内容
    if(_elem != NULL){
        delete [] _elem;
    }

    copyFrom(V._elem,0,V._size);
    return *this;
}

// ##############################################################################################################################
/**
 * 动态空间管理部分
 * 扩容 缩容
 */

template <typename T>
void Vector<T>::expand() {
    if(_size < _capacity)  return;

    if(_capacity < DEFAULT_CAPACITY) _capacity = DEFAULT_CAPACITY;

    T* new_elem = new T[_capacity <<= 1]; // 扩容两倍

    for(int i=0; i<_size; i++){
        new_elem[i] = _elem[i];
    }
    // 删除就的内容
    delete [] _elem;
    _elem = new_elem;
    return;
}

template <typename T>
void Vector<T>::shrink() {
    if(_capacity <= DEFAULT_CAPACITY ) return;

    if(_size << 2 > _capacity) return;   // _size 需要小于 _capacity 的 1/4 才缩容

    T* new_elem = new T[_capacity >>= 1]; // 扩容两倍

    for(int i=0; i<_size; i++){
        new_elem[i] = _elem[i];
    }
    // 删除就的内容
    delete [] _elem;
    _elem = new_elem;
    return;
}

// 插入 删除部分

/**
 * 插入算法需要把后面的元素向后挪动, 算法的复杂度取决与插入的位置
 * @tparam T
 * @param r
 * @param e
 * @return
 */
template <typename T>
Rank Vector<T>::insert(Rank r, const T &e) {
    if(r < 0) r = 0;
    if(r>_size) r = _size;

    expand();

    for(int i=_size; i> r;i--){
        _elem[i] = _elem[i-1];
    }
    _elem[r] = e;
    _size ++;
    return r;
}

/**
 * @return  删除的元素的数量
 */
template <typename T>
int Vector<T>::remove(Rank lo, Rank hi) {
    if(lo == hi) return 0;

    while (hi <_size){
        _elem[lo++] = _elem[hi++];
        _size --;
    }

    shrink(); // 必要时缩容
    return hi - lo;
}

/**
 * @return  被删除的元素的值
 */
template <typename T>
T Vector<T>::remove(Rank r) {
    T e = _elem[r];
    remove(r,r+1);
    return e;
}

//==============================================================================================================



/**
 * 随机置乱算法
 */

template <typename T>
void permute(Vector<T> & V){
    for(int i=V.size(); i>0;i--){
        /**
         *
         *  这里用到了 Knuth 洗牌算法 原理
         *  12345
         *  15342   2被选择在位置5的概率为1/5
         *  15432   2被选择在位置5的概率为4/5 * 1/4 = 1/5
         */
        myswap(V[i-1], V[rand()%i]);
    }
}
template <typename T>
void Vector<T>::unsort(Rank lo, Rank hi) {
    T* V = _elem + lo;

    for(int i = hi-lo; i>0; i--){
        myswap(V[i-1], V[rand()%i]);
    }
}

/**
 *  无序查找 [lo, hi)
 * @return  成功返回最后一个找到的元素索引， 失败返回lo-1
 */
template <typename T>
Rank Vector<T>::find(const T &e, Rank lo, Rank hi) const {
    for(int i=hi-1; i>=lo; i--){
        if(e == _elem[i]){
            return i;
        }
    }
    return lo-1;
}

/**
 * 无序变量的唯一化
 * @tparam T
 * @return
 */
template <typename T>
Rank Vector<T>::deduplicate() {
    int oldSize = _size;

    int i = 1;
    while (i < _size){
        if(find(_elem[i], 0, i) < 0){
            i++;
        }else{
            remove(i);
        }
    }
}

//====================================================================
// 容量的遍历
template <typename T>
void Vector<T>::traverse(void (*visit)(T &)) {
    for(int i=0; i<_size; i++){
        visit(_elem[i]);
    }
}


template <typename T>
template<typename VST>
void Vector<T>::traverse(VST & visit) {
    for(int i=0; i<_size; i++){
        visit(_elem[i]);
    }
}


// ===============================================
// 有序变量相关算法
/**
 *
 * @tparam T
 * @return  返回逆序数
 */
template <typename T>
int Vector<T>::disordered() const {
    int n = 0;
    for(int i=1; i<_size; i++){
        if(_elem[i-1] > _elem[i]){
            n++;
        }
    }
    return n;
}

/**
 * 有序变量唯一化
 * @tparam T
 * @return
 *
 *
 *   i        j
 * 1 3 3 3 3 5
 */
template <typename T>
int Vector<T>::uniquify() {
    int i=0, j=1;

    while (j<_size){
        if((_elem[i] != _elem[j])){
            _elem[++i] = _elem[j];
        }
        j++;
    }
    _size = i++;
    shrink();
    return j-i;

}
template <typename T>
Rank Vector<T>::search(const T &e, Rank lo, Rank hi) const {
    return binSearch(_elem, e, lo, hi);
}


#endif //CPP_LEARNING_VECTOR_HPP
